package _interview100;

import java.util.HashMap;

/**
 * 146. LRU 缓存
 */
public class No146 {
    private final HashMap<Integer, Node> DB;
    private final int capacity;
    private final Node dummy;

    public No146(int capacity) {
        DB = new HashMap<>();
        this.capacity = capacity;
        dummy = new Node();
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        if (!DB.containsKey(key)) return -1;
        Node node = this.getNode(key);
        return node.value;
    }

    public void put(int key, int value) {
        if (DB.containsKey(key)) {
            Node node = this.getNode(key);
            node.value = value;
            return;
        }
        if (DB.size() == capacity) {
            Node lastNode = dummy.prev;
            this.removeNode(lastNode);
            DB.remove(lastNode.key);
        }
        Node node = new Node(key, value);
        this.putNode(node);
        DB.put(key, node);
    }

    private Node getNode(int key) {
        Node node = DB.get(key);
        this.removeNode(node);
        this.putNode(node);
        return node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void putNode(Node node) {
        node.prev = dummy;
        node.next = dummy.next;
        node.prev.next = node;
        node.next.prev = node;
    }

    private static class Node {
        private int key, value;
        private Node prev, next;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
